package org.example.sword2offer.primary;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;

/**
 * @author: lynn
 * @Descript: 和为S的两个数字
 * @date: 2021/3/21 21:36
 * 输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，
 * 如果有多对数字的和等于S，输出两个数的乘积最小的。
 * @version: 1.0
 */
public class Q42_FindNumbersWithSum {

    public static void main(String[] args) {
        int[] array={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};
        System.out.println(FindNumbersWithSum(array,21));
    }

    /**
    *  如果两指针元素之和大于sum，那么将r指针左移，试图减小两指针之和
     * 如果两指针元素之和小于sum，那么将l右移，试图增大两指针之和
     * 如果两指针元素之和等于sum那么就可以返回了，或者r跑到了l的左边表名没有和sum的两个数，也可以返回了。
     *
     */

    private static ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        ArrayList<Integer> arrayList=new ArrayList<>();

        int l=0,r=array.length-1;
        while (l<r){
            if (array[l]+array[r]>sum){
                r--;
            }else if (array[l]+array[r]<sum){
                l++;
            }else {
                if (arrayList.size()==0){
                    arrayList.add(array[l]);
                    arrayList.add(array[r]);
                }
                if (arrayList.get(0)*arrayList.get(1)>array[l]*array[r]){
                    arrayList.clear();
                    arrayList.add(array[l]);
                    arrayList.add(array[r]);
                }
                l++;
            }
        }
        return arrayList;
    }
}
